package niuke.week3;

import java.util.Scanner;

/**
 给定一个字符串str，再给定str的最长回文子序列字符串strlps,
 请返回在添加字符最少的情况下，让str整体都是回文字符串的一种结果。

 进阶问题比原问题多了一个参数，请做到时间复杂度比原问题的实现低。

 输入
 A1B21C
 121
 输出
 AC1B2B1CA

 */
public class AddCharGetHuiWenChuanAdvance {

    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        String next = sc.next();
        char[] chars = next.toCharArray();
        
        String str2 = sc.next();
        char[] lps = str2.toCharArray();

        //指向原数组
        int charl = 0;
        int charr = chars.length - 1;
        //指向子序列数组
        int lpsl = 0;
        int lpsr = lps.length - 1;

        char[] res = new char[2 * chars.length - lps.length];
        int resl = 0;
        int resr = res.length - 1;

        int tmpl = 0;
        int tmpr = 0;

        while (lpsl <= lpsr) {
            tmpl = charl;
            tmpr = charr;

            while (chars[charl] != lps[lpsl]) {//找到子序列第一个字符的位置
                charl++;
            }

            while (chars[charr] != lps[lpsr]) {//找到子序列最后一个字符的位置
                charr--;
            }

            //先搞定不是回文的地方
            set(res,
                    resl, resr,
                    chars,
                    tmpl,charl,//左边不是回文串的区间
                    charr,tmpr);//右边不是回文串的区间

            //      左边的个数         右边的个数
            resl += charl - tmpl + tmpr - charr;
            resr -= charl - tmpl + tmpr - charr;
            //拷贝回文串两端相等的地方
            res[resl++] = chars[charl++];
            res[resr--] = chars[charr--];
            //取出掉已经计算过的回文子序列
            lpsl++;
            lpsr--;
        }
        System.out.println(String.valueOf(res));
    }

    public static void set(char[] res,
                           int resl, int resr,
                           char[] chas,
                           int ls, int le, //左边开始到结尾
                           int rs,int re) {//右边开始到结尾

        for (int i = ls; i < le; i++) {//把原字符值拷贝到res : [ls...le)--->[ls...le-1      le-1...ls]
            res[resl++] = chas[i];
            res[resr--] = chas[i];
        }
        for (int i = re; i > rs; i--) {//把原字符值拷贝到res : (rs...re]--->[re...rs-1      rs-1...re]
            res[resl++] = chas[i];
            res[resr--] = chas[i];
        }
    }
}